package bst;

/**
 * @description: 二叉排序树
 * @author: wangjun
 * @create: 2022-05-03
 */
public class BinarySortTreeMain {
    public static void main(String[] args) {
        BinarySortTree sortTree = new BinarySortTree();
        int[] array = {7, 3, 10, 12, 5, 1, 9, 2};
        for (int value : array) {
            sortTree.add(new Node(value));
        }
        System.out.println("未删除节点之前，中序遍历：");
        sortTree.infixOrderPrint();
        System.out.println("删除节点之后，中序遍历：");
        sortTree.delNode(10);
        sortTree.infixOrderPrint();
    }
}

class BinarySortTree {
    private Node root;

    public void add(Node node) {
        if (root == null) {
            root = node;
            return;
        }
        root.add(node);
    }

    public void infixOrderPrint() {
        if (root == null) {
            System.out.println("树为空");
            return;
        }
        root.infixOrderPrint();
    }

    public Node search(int value) {
        if (root == null) {
            return null;
        }
        return root.search(value);
    }

    public Node searchParent(int value) {
        if (root == null) {
            return null;
        }
        return root.searchNodeParent(value);
    }

    public void delNode(int nodeValue) {
        if (root == null) {
            return;
        }
        Node targetNode = search(nodeValue);
        if (targetNode == null) {
            System.out.println("没有找到要删除的结点");
            return;
        }
        // 判断是不是只有一个节点的树
        if (root.left == null && root.right == null) {
            root = null;
            return;
        }
        Node parent = searchParent(nodeValue);
        // 如果要删除的结点是叶子结点
        if (targetNode.left == null && targetNode.right == null) {
            // 是父节点的左子节点
            if (parent.left != null && parent.left.val == nodeValue) {
                parent.left = null;
                return;
            }
            // 是父节点的右子节点
            if (parent.right != null && parent.right.val == nodeValue) {
                parent.right = null;
            }
        } else if (targetNode.left != null && targetNode.right != null) {
            //如果要删除的结点左右子树都不为空
            targetNode.val = minValueByRightTree(targetNode.right);
        } else {
            // 如果要删除的结点只有一个左子树
            if (targetNode.left != null) {
                if (parent == null) {
                    root = targetNode.left;
                } else {
                    // 判断是在parent的左边还是右边
                    if (parent.left.val == nodeValue) {
                        parent.left = targetNode.left;
                    } else if (parent.right.val == nodeValue) {
                        parent.right = targetNode.left;
                    }
                }
            } else {
                //如果要删除的结点只有一个右子树
                if (parent == null) {
                    root = targetNode.right;
                } else {
                    if (parent.left.val == nodeValue) {
                        parent.left = targetNode.right;
                    } else {
                        parent.right = targetNode.right;
                    }
                }
            }
        }
    }

    public int minValueByRightTree(Node node) {
        Node temp = node;
        while (temp.left != null) {
            temp = temp.left;
        }
        // 删除右子树中最小值节点
        delNode(temp.val);
        // 返回右子树最小值
        return temp.val;
    }
}


class Node {
    public int val;
    public Node left;
    public Node right;

    public Node(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }

    public void add(Node node) {
        // 如果当前节点的值小于传递的node节点的值，则在右子树
        if (this.val < node.val) {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        } else {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        }
    }

    /**
     * 查找要删除的结点
     *
     * @param [value]
     * @return bst.Node
     */
    public Node search(int value) {
        if (this.val == value) {
            return this;
        }
        if (value < this.val) {
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else {
            if (this.right == null) {
                return null;
            }
            return this.right.search(value);
        }
    }

    /**
     * 查找待删除结点的父节点
     *
     * @param [value]
     * @return bst.Node
     */
    public Node searchNodeParent(int value) {
        if (this.left != null && this.left.val == value) {
            return this;
        }
        if (this.right != null && this.right.val == value) {
            return this;
        }
        if (value < this.val && this.left != null) {
            return this.left.searchNodeParent(value);
        } else if (value >= this.val && this.right != null) {
            return this.right.searchNodeParent(value);
        } else {
            return null;
        }
    }

    public void infixOrderPrint() {
        if (this.left != null) {
            this.left.infixOrderPrint();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrderPrint();
        }
    }
}